Micron Document
<!DOCTYPE html>
<html class="client-nojs vector-feature-night-mode-disabled vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-sticky-header-enabled" lang="en" dir="ltr"><head>
<meta charset="UTF-8">
<title>Symmetric Boolean function</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="canonical" href="https://en.wikipedia.org/wiki/Symmetric_Boolean_function"> <link href="./mw/ext.cite.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/ext.math.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/user.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link rel="stylesheet" type="text/css" href="./mw/site.styles.css">
<link rel="stylesheet" type="text/css" href="./mw/noscript.css">
<link rel="stylesheet" type="text/css" href="./footer.css">
<link rel="stylesheet" type="text/css" href="./vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Symmetric_Boolean_function rootpage-Symmetric_Boolean_function skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading">
<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Symmetric Boolean function</span></span>
</h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><p>In <a href="Mathematics" title="Mathematics">mathematics</a>, a <b>symmetric Boolean function</b> is a <a href="Boolean_function" title="Boolean function">Boolean function</a> whose value does not depend on the <a href="Permutation" title="Permutation">order</a> of its input bits, i.e., it depends only on the number of ones (or zeros) in the input.<sup id="cite_ref-weg_1-0" class="reference"><a href="#cite_note-weg-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> For this reason they are also known as <b>Boolean counting functions</b>.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>
</p><p>There are 2<sup><i>n</i>+1</sup> symmetric <i>n</i>-ary Boolean functions. Instead of the <a href="Truth_table" title="Truth table">truth table</a>, traditionally used to represent Boolean functions, one may use a more compact representation for an <i>n</i>-variable symmetric Boolean function: the (<i>n</i>&nbsp;+&nbsp;1)-vector, whose <i>i</i>-th entry (<i>i</i>&nbsp;=&nbsp;0,&nbsp;...,&nbsp;<i>n</i>) is the value of the function on an input vector with <i>i</i> ones. Mathematically, the symmetric Boolean functions correspond one-to-one with the functions that map <i>n+1</i> elements to two elements, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:\{0,1,...,n\}\rightarrow \{0,1\}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>f</mi>
<mo>:</mo>
<mo fence="false" stretchy="false">{</mo>
<mn>0</mn>
<mo>,</mo>
<mn>1</mn>
<mo>,</mo>
<mo>.</mo>
<mo>.</mo>
<mo>.</mo>
<mo>,</mo>
<mi>n</mi>
<mo fence="false" stretchy="false">}</mo>
<mo stretchy="false">→<!-- → --></mo>
<mo fence="false" stretchy="false">{</mo>
<mn>0</mn>
<mo>,</mo>
<mn>1</mn>
<mo fence="false" stretchy="false">}</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle f:\{0,1,...,n\}\rightarrow \{0,1\}}</annotation>
</semantics>
</math></span><img src="./954242e4f79bbd39338477ff9092dbf06acbd39e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.762ex; height:2.843ex;" alt="{\displaystyle f:\{0,1,...,n\}\rightarrow \{0,1\}}" loading="lazy"></span>.
</p><p>Symmetric Boolean functions are used to classify <a href="Boolean_satisfiability_problem" title="Boolean satisfiability problem">Boolean satisfiability problems</a>.
</p>
<meta property="mw:PageProp/toc">
<div class="mw-heading mw-heading2"><h2 id="Special_cases">Special cases</h2></div>
<p>A number of special cases are recognized:<sup id="cite_ref-weg_1-1" class="reference"><a href="#cite_note-weg-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>
</p>
<ul><li><b><a href="Majority_function" title="Majority function">Majority function</a></b>: their value is 1 on input vectors with more than n/2 ones</li>
<li><b>Threshold functions</b>: their value is 1 on input vectors with <i>k</i> or more ones for a fixed <i>k</i></li>
<li><b>All-equal</b> and <b>not-all-equal function</b>: their values is 1 when the inputs do (not) all have the same value</li>
<li><b>Exact-count functions</b>: their value is 1 on input vectors with <i>k</i> ones for a fixed <i>k</i>
<ul><li><b><a href="One-hot" title="One-hot">One-hot</a></b> or <b>1-in-n function</b>: their value is 1 on input vectors with exactly one one</li>
<li><b>One-cold function</b>: their value is 1 on input vectors with exactly one zero</li></ul></li>
<li><b>Congruence functions</b>: their value is 1 on input vectors with the number of ones congruent to <i>k</i>&nbsp;mod&nbsp;<i>m</i> for fixed <i>k</i>,&nbsp;<i>m</i></li>
<li><b><a href="Parity_function" title="Parity function">Parity function</a></b>: their value is 1 if the input vector has odd number of ones</li></ul>
<p>The n-ary versions of <a href="AND_gate" title="AND gate">AND</a>, <a href="OR_gate" title="OR gate">OR</a>, <a href="XOR_gate" title="XOR gate">XOR</a>, <a href="NAND_gate" title="NAND gate">NAND</a>, <a href="NOR_gate" title="NOR gate">NOR</a> and <a href="XNOR_gate" title="XNOR gate">XNOR</a> are also symmetric Boolean functions.
</p>
<div class="mw-heading mw-heading2"><h2 id="Properties">Properties</h2></div>
<p>In the following, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{k}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>f</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>k</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle f_{k}}</annotation>
</semantics>
</math></span><img src="./8a585492f646ca803bc408103a0c705dd67ab8b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.228ex; height:2.509ex;" alt="{\displaystyle f_{k}}" loading="lazy"></span> denotes the value of the function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>f</mi>
<mo>:</mo>
<mo fence="false" stretchy="false">{</mo>
<mn>0</mn>
<mo>,</mo>
<mn>1</mn>
<msup>
<mo fence="false" stretchy="false">}</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
<mo stretchy="false">→<!-- → --></mo>
<mo fence="false" stretchy="false">{</mo>
<mn>0</mn>
<mo>,</mo>
<mn>1</mn>
<mo fence="false" stretchy="false">}</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}}</annotation>
</semantics>
</math></span><img src="./d46c9deab62ff34adb9aa344f490e928f3fbac1d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.416ex; height:2.843ex;" alt="{\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}}" loading="lazy"></span> when applied to an input vector of <a href="Hamming_weight" title="Hamming weight">weight</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>k</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k}</annotation>
</semantics>
</math></span><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span>.
</p>
<div class="mw-heading mw-heading3"><h3 id="Weight">Weight</h3></div>
<p>The weight of the function can be calculated from its value vector:
</p><p><span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |f|=\sum _{k=0}^{n}{\binom {n}{k}}f_{k}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mo stretchy="false">|</mo>
</mrow>
<mi>f</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo stretchy="false">|</mo>
</mrow>
<mo>=</mo>
<munderover>
<mo>∑<!-- ∑ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>k</mi>
<mo>=</mo>
<mn>0</mn>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</munderover>
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mrow class="MJX-TeXAtom-OPEN">
<mo maxsize="2.047em" minsize="2.047em">(</mo>
</mrow>
<mfrac linethickness="0">
<mi>n</mi>
<mi>k</mi>
</mfrac>
<mrow class="MJX-TeXAtom-CLOSE">
<mo maxsize="2.047em" minsize="2.047em">)</mo>
</mrow>
</mrow>
</mrow>
<msub>
<mi>f</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>k</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle |f|=\sum _{k=0}^{n}{\binom {n}{k}}f_{k}}</annotation>
</semantics>
</math></span></span>
</p>
<div class="mw-heading mw-heading3"><h3 id="Algebraic_normal_form">Algebraic normal form</h3></div>
<p>The <a href="Algebraic_normal_form" title="Algebraic normal form">algebraic normal form</a> either contains all monomials of certain order <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>m</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle m}</annotation>
</semantics>
</math></span><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"></span>, or none of them; i.e. the <a href="Zhegalkin_polynomial#Möbius_transformation" title="Zhegalkin polynomial">Möbius transform</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {f}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mover>
<mi>f</mi>
<mo stretchy="false">^<!-- ^ --></mo>
</mover>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\hat {f}}}</annotation>
</semantics>
</math></span><img src="./14ce989fd75da938ec6f95a0cdb71037b23a11cb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.699ex; height:3.176ex;" alt="{\displaystyle {\hat {f}}}" loading="lazy"></span> of the function is also a symmetric function. It can thus also be described by a simple (<i>n</i>+1) bit vector, the <i>ANF vector</i> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {f}}_{m}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mover>
<mi>f</mi>
<mo stretchy="false">^<!-- ^ --></mo>
</mover>
</mrow>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi>m</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\hat {f}}_{m}}</annotation>
</semantics>
</math></span><img src="./87de15f8d9bdfde8d1551898378dcc0eaec77140.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.374ex; height:3.343ex;" alt="{\displaystyle {\hat {f}}_{m}}" loading="lazy"></span>. The ANF and value vectors are related by a Möbius relation:<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {f}}_{m}=\bigoplus _{k_{2}\subseteq m_{2}}f_{k}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mover>
<mi>f</mi>
<mo stretchy="false">^<!-- ^ --></mo>
</mover>
</mrow>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi>m</mi>
</mrow>
</msub>
<mo>=</mo>
<munder>
<mo>⨁<!-- ⨁ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>k</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>⊆<!-- ⊆ --></mo>
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
</mrow>
</munder>
<msub>
<mi>f</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>k</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\hat {f}}_{m}=\bigoplus _{k_{2}\subseteq m_{2}}f_{k}}</annotation>
</semantics>
</math></span></span>where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{2}\subseteq m_{2}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>k</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>⊆<!-- ⊆ --></mo>
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k_{2}\subseteq m_{2}}</annotation>
</semantics>
</math></span><img src="./d637d127714d25fc196ef484fc92c889bfcb2e1c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.459ex; height:2.509ex;" alt="{\displaystyle k_{2}\subseteq m_{2}}" loading="lazy"></span> denotes all the weights <i>k</i> whose <a href="Base_2" class="mw-redirect" title="Base 2">base-2</a> representation is covered by the base-2 representation of <i>m</i> (a consequence of <a href="Lucas's_theorem" title="Lucas's theorem">Lucas’ theorem</a>).<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> Effectively, an n-variable symmetric Boolean function corresponds to a log(n)-variable ordinary <a href="Boolean_function" title="Boolean function">Boolean function</a> acting on the base-2 representation of the input weight.
</p><p>For example, for three-variable functions:
</p><p><span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{array}{lcl}{\hat {f}}_{0}&amp;=&amp;f_{0}\\{\hat {f}}_{1}&amp;=&amp;f_{0}\oplus f_{1}\\{\hat {f}}_{2}&amp;=&amp;f_{0}\oplus f_{2}\\{\hat {f}}_{3}&amp;=&amp;f_{0}\oplus f_{1}\oplus f_{2}\oplus f_{3}\end{array}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mtable columnalign="left center left" rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<msub>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mover>
<mi>f</mi>
<mo stretchy="false">^<!-- ^ --></mo>
</mover>
</mrow>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mn>0</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mo>=</mo>
</mtd>
<mtd>
<msub>
<mi>f</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>0</mn>
</mrow>
</msub>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mover>
<mi>f</mi>
<mo stretchy="false">^<!-- ^ --></mo>
</mover>
</mrow>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mo>=</mo>
</mtd>
<mtd>
<msub>
<mi>f</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>0</mn>
</mrow>
</msub>
<mo>⊕<!-- ⊕ --></mo>
<msub>
<mi>f</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mover>
<mi>f</mi>
<mo stretchy="false">^<!-- ^ --></mo>
</mover>
</mrow>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mo>=</mo>
</mtd>
<mtd>
<msub>
<mi>f</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>0</mn>
</mrow>
</msub>
<mo>⊕<!-- ⊕ --></mo>
<msub>
<mi>f</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mover>
<mi>f</mi>
<mo stretchy="false">^<!-- ^ --></mo>
</mover>
</mrow>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mo>=</mo>
</mtd>
<mtd>
<msub>
<mi>f</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>0</mn>
</mrow>
</msub>
<mo>⊕<!-- ⊕ --></mo>
<msub>
<mi>f</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>⊕<!-- ⊕ --></mo>
<msub>
<mi>f</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>⊕<!-- ⊕ --></mo>
<msub>
<mi>f</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msub>
</mtd>
</mtr>
</mtable>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{array}{lcl}{\hat {f}}_{0}&amp;=&amp;f_{0}\\{\hat {f}}_{1}&amp;=&amp;f_{0}\oplus f_{1}\\{\hat {f}}_{2}&amp;=&amp;f_{0}\oplus f_{2}\\{\hat {f}}_{3}&amp;=&amp;f_{0}\oplus f_{1}\oplus f_{2}\oplus f_{3}\end{array}}}</annotation>
</semantics>
</math></span></span>
</p><p>So the three variable <a href="Majority_function" title="Majority function">majority function</a> with value vector (0, 0, 1, 1) has ANF vector (0, 0, 1, 0), i.e.:<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{Maj}}(x,y,z)=xy\oplus xz\oplus yz}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mtext>Maj</mtext>
</mrow>
<mo stretchy="false">(</mo>
<mi>x</mi>
<mo>,</mo>
<mi>y</mi>
<mo>,</mo>
<mi>z</mi>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mi>x</mi>
<mi>y</mi>
<mo>⊕<!-- ⊕ --></mo>
<mi>x</mi>
<mi>z</mi>
<mo>⊕<!-- ⊕ --></mo>
<mi>y</mi>
<mi>z</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\text{Maj}}(x,y,z)=xy\oplus xz\oplus yz}</annotation>
</semantics>
</math></span></span>
</p>
<div class="mw-heading mw-heading3"><h3 id="Unit_hypercube_polynomial">Unit hypercube polynomial</h3></div>
<p>The coefficients of the real polynomial agreeing with the function on <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{0,1\}^{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo fence="false" stretchy="false">{</mo>
<mn>0</mn>
<mo>,</mo>
<mn>1</mn>
<msup>
<mo fence="false" stretchy="false">}</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \{0,1\}^{n}}</annotation>
</semantics>
</math></span><img src="./3cc07e486d73e18382d0d8d205149f0923ed0586.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.902ex; height:2.843ex;" alt="{\displaystyle \{0,1\}^{n}}" loading="lazy"></span> are given by:<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{m}^{*}=\sum _{k=0}^{m}(-1)^{|k|+|m|}{\binom {m}{k}}f_{k}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msubsup>
<mi>f</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>m</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mo>∗<!-- ∗ --></mo>
</mrow>
</msubsup>
<mo>=</mo>
<munderover>
<mo>∑<!-- ∑ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>k</mi>
<mo>=</mo>
<mn>0</mn>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi>m</mi>
</mrow>
</munderover>
<mo stretchy="false">(</mo>
<mo>−<!-- − --></mo>
<mn>1</mn>
<msup>
<mo stretchy="false">)</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mo stretchy="false">|</mo>
</mrow>
<mi>k</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo stretchy="false">|</mo>
</mrow>
<mo>+</mo>
<mrow class="MJX-TeXAtom-ORD">
<mo stretchy="false">|</mo>
</mrow>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo stretchy="false">|</mo>
</mrow>
</mrow>
</msup>
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mrow class="MJX-TeXAtom-OPEN">
<mo maxsize="2.047em" minsize="2.047em">(</mo>
</mrow>
<mfrac linethickness="0">
<mi>m</mi>
<mi>k</mi>
</mfrac>
<mrow class="MJX-TeXAtom-CLOSE">
<mo maxsize="2.047em" minsize="2.047em">)</mo>
</mrow>
</mrow>
</mrow>
<msub>
<mi>f</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>k</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle f_{m}^{*}=\sum _{k=0}^{m}(-1)^{|k|+|m|}{\binom {m}{k}}f_{k}}</annotation>
</semantics>
</math></span></span>For example, the three variable <a href="Majority_function" title="Majority function">majority function</a> polynomial has coefficients (0, 0, 1, -2):<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{Maj}}(x,y,z)=(xy+xz+yz)-2(xyz)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mtext>Maj</mtext>
</mrow>
<mo stretchy="false">(</mo>
<mi>x</mi>
<mo>,</mo>
<mi>y</mi>
<mo>,</mo>
<mi>z</mi>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mo stretchy="false">(</mo>
<mi>x</mi>
<mi>y</mi>
<mo>+</mo>
<mi>x</mi>
<mi>z</mi>
<mo>+</mo>
<mi>y</mi>
<mi>z</mi>
<mo stretchy="false">)</mo>
<mo>−<!-- − --></mo>
<mn>2</mn>
<mo stretchy="false">(</mo>
<mi>x</mi>
<mi>y</mi>
<mi>z</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\text{Maj}}(x,y,z)=(xy+xz+yz)-2(xyz)}</annotation>
</semantics>
</math></span></span>
</p>
<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>
<table class="wikitable">
<caption>The 16 symmetric Boolean functions of three variables
</caption>
<tbody><tr>
<th colspan="4">Function value
</th>
<th rowspan="2">Value vector
</th>
<th rowspan="2">Weight
</th>
<th rowspan="2">Name
</th>
<th rowspan="2">Colloquial description
</th>
<th rowspan="2">ANF vector
</th></tr>
<tr>
<th>0
</th>
<th>1
</th>
<th>2
</th>
<th>3
</th></tr>
<tr>
<td>F
</td>
<td>F
</td>
<td>F
</td>
<td>F
</td>
<td>(0, 0, 0, 0)
</td>
<td>0
</td>
<td>Constant false
</td>
<td>"never"
</td>
<td>(0, 0, 0, 0)
</td></tr>
<tr>
<td>F
</td>
<td>F
</td>
<td>F
</td>
<td>T
</td>
<td>(0, 0, 0, 1)
</td>
<td>1
</td>
<td>Three-way <a href="AND_gate" title="AND gate">AND</a>, Threshold(3), Count(3)
</td>
<td>"all three"
</td>
<td>(0, 0, 0, 1)
</td></tr>
<tr>
<td>F
</td>
<td>F
</td>
<td>T
</td>
<td>F
</td>
<td>(0, 0, 1, 0)
</td>
<td>3
</td>
<td>Count(2), One-cold
</td>
<td>"exactly two"
</td>
<td>(0, 0, 1, 1)
</td></tr>
<tr>
<td>F
</td>
<td>F
</td>
<td>T
</td>
<td>T
</td>
<td>(0, 0, 1, 1)
</td>
<td>4
</td>
<td>Majority, Threshold(2)
</td>
<td>"most", "at least two"
</td>
<td>(0, 0, 1, 0)
</td></tr>
<tr>
<td>F
</td>
<td>T
</td>
<td>F
</td>
<td>F
</td>
<td>(0, 1, 0, 0)
</td>
<td>3
</td>
<td>Count(1), One-hot
</td>
<td>"exactly one"
</td>
<td>(0, 1, 0, 1)
</td></tr>
<tr>
<td>F
</td>
<td>T
</td>
<td>F
</td>
<td>T
</td>
<td>(0, 1, 0, 1)
</td>
<td>4
</td>
<td>Three-way <a href="XOR_gate" title="XOR gate">XOR</a>, (odd) <a href="Parity_function" title="Parity function">parity</a>
</td>
<td>"one or three"
</td>
<td>(0, 1, 0, 0)
</td></tr>
<tr>
<td>F
</td>
<td>T
</td>
<td>T
</td>
<td>F
</td>
<td>(0, 1, 1, 0)
</td>
<td>6
</td>
<td>Not-all-equal
</td>
<td>"one or two"
</td>
<td>(0, 1, 1, 0)
</td></tr>
<tr>
<td>F
</td>
<td>T
</td>
<td>T
</td>
<td>T
</td>
<td>(0, 1, 1, 1)
</td>
<td>7
</td>
<td>Three-way <a href="OR_gate" title="OR gate">OR</a>, Threshold(1)
</td>
<td>"any", "at least one"
</td>
<td>(0, 1, 1, 1)
</td></tr>
<tr>
<td>T
</td>
<td>F
</td>
<td>F
</td>
<td>F
</td>
<td>(1, 0, 0, 0)
</td>
<td>1
</td>
<td>Three-way <a href="NOR_gate" title="NOR gate">NOR</a>, Count(0)
</td>
<td>"none"
</td>
<td>(1, 1, 1, 1)
</td></tr>
<tr>
<td>T
</td>
<td>F
</td>
<td>F
</td>
<td>T
</td>
<td>(1, 0, 0, 1)
</td>
<td>2
</td>
<td>All-equal
</td>
<td>"all or none"
</td>
<td>(1, 1, 1, 0)
</td></tr>
<tr>
<td>T
</td>
<td>F
</td>
<td>T
</td>
<td>F
</td>
<td>(1, 0, 1, 0)
</td>
<td>4
</td>
<td>Three-way <a href="XNOR_gate" title="XNOR gate">XNOR</a>, <a href="Parity_(mathematics)" title="Parity (mathematics)">even parity</a>
</td>
<td>"none or two"
</td>
<td>(1, 1, 0, 0)
</td></tr>
<tr>
<td>T
</td>
<td>F
</td>
<td>T
</td>
<td>T
</td>
<td>(1, 0, 1, 1)
</td>
<td>5
</td>
<td>
</td>
<td>"not exactly one"
</td>
<td>(1, 1, 0, 1)
</td></tr>
<tr>
<td>T
</td>
<td>T
</td>
<td>F
</td>
<td>F
</td>
<td>(1, 1, 0, 0)
</td>
<td>4
</td>
<td>(<a href="Horn_clause" title="Horn clause">Horn clause</a>)
</td>
<td>"at most one"
</td>
<td>(1, 0, 1, 0)
</td></tr>
<tr>
<td>T
</td>
<td>T
</td>
<td>F
</td>
<td>T
</td>
<td>(1, 1, 0, 1)
</td>
<td>5
</td>
<td>
</td>
<td>"not exactly two"
</td>
<td>(1, 0, 1, 1)
</td></tr>
<tr>
<td>T
</td>
<td>T
</td>
<td>T
</td>
<td>F
</td>
<td>(1, 1, 1, 0)
</td>
<td>7
</td>
<td>Three-way <a href="NAND_gate" title="NAND gate">NAND</a>
</td>
<td>"at most two"
</td>
<td>(1, 0, 0, 1)
</td></tr>
<tr>
<td>T
</td>
<td>T
</td>
<td>T
</td>
<td>T
</td>
<td>(1, 1, 1, 1)
</td>
<td>8
</td>
<td>Constant true
</td>
<td>"always"
</td>
<td>(1, 0, 0, 0)
</td></tr></tbody></table>
<div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2></div>
<ul><li><a href="Symmetric_function" title="Symmetric function">Symmetric function</a></li></ul>
<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>
<style data-mw-deduplicate="TemplateStyles:r1239543626">
/* start https://en.wikipedia.org/ */


.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}


/* end https://en.wikipedia.org/ */
</style><div class="reflist">
<div class="mw-references-wrap"><ol class="references">
<li id="cite_note-weg-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-weg_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-weg_1-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><a href="Ingo_Wegener" title="Ingo Wegener">Ingo Wegener</a>, "The Complexity of Symmetric Boolean Functions", in: <i>Computation Theory and Logic</i>, <i><a href="Lecture_Notes_in_Computer_Science" title="Lecture Notes in Computer Science">Lecture Notes in Computer Science</a></i>, vol. 270, 1987, pp. 433–442</span>
</li>
<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">
/* start https://en.wikipedia.org/ */


.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}


/* end https://en.wikipedia.org/ */
</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://reference.wolfram.com/language/ref/BooleanCountingFunction.html.en">"BooleanCountingFunction—Wolfram Language Documentation"</a>. <i>reference.wolfram.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2021-05-25</span></span>.</cite></span>
</li>
<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFCanteautVideau2005" class="citation journal cs1">Canteaut, A.; Videau, M. (2005). <a rel="nofollow" class="external text" href="https://hal.inria.fr/inria-00001148/document">"Symmetric Boolean functions"</a>. <i>IEEE Transactions on Information Theory</i>. <b>51</b> (8): <span class="nowrap">2791–</span>2811. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTIT.2005.851743">10.1109/TIT.2005.851743</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a>&nbsp;<a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1557-9654">1557-9654</a>.</cite></span>
</li>
</ol></div></div></div><!--htdig_noindex--><div><div class="zim-footer">
This article is issued from <a class="external text" title="Last edited on 2025-01-14" href="https://en.wikipedia.org/wiki/?title=Symmetric_Boolean_function&amp;oldid=1269337611">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>

</body></html>